/**
 * Created with IntelliJ IDEA
 * Description:
 * User: lenovo
 * Date: 2023 -05 -06
 * Time: 17:19
 */
public class InsertionSorting {
    public static void InsertionSorting(int[] array){
        for (int i = 1; i < array.length ; i++) {
            int tmp=array[i];
            int j = i-1;
            for (j = i-1; j >=0 ; j--) {
                if(array[j]>tmp){
                    array[j+1]=array[j];
                    array[j]=tmp;
                }else{
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }
    public static void main(String[] args) {
        int[] array=new int[]{1,5,3,9,8,4};
        InsertionSorting(array);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+" ");
        }
    }
}
